package leetcode.lt题型分类.并查集;

import org.junit.Test;

/**
 * @author ：zsy
 * @date ：Created 2022/10/17 7:43 PM
 * @description：https://leetcode.cn/problems/number-of-provinces/
 */
public class 省份数量 {
    @Test
    public void test() {

    }

    class Solution {
        public int findCircleNum(int[][] isConnected) {
            int provinces = isConnected.length;
            int[] parent = new int[provinces];
            int[] rank = new int[provinces];
            for (int i = 0; i < provinces; i++) {
                parent[i] = i;
            }
            for (int i = 0; i < provinces; i++) {
                for (int j = 0; j < isConnected[i].length; j++) {
                    if (isConnected[i][j] == 1) {
                        unionVertices(parent, rank, i, j);
                    }
                }
            }
            int ans = 0;
            for (int i = 0; i < provinces; i++) {
                if (parent[i] == i) {
                    ans++;
                }
            }
            return ans;
        }

        private void unionVertices(int[] parent, int[] rank, int x, int y) {
            int x_root = findRoot(parent, x);
            int y_root = findRoot(parent, y);
            if (x_root == y_root) return;
            if (rank[x_root] > rank[y_root]) {
                parent[y_root] = x_root;
            } else if (rank[x_root] < rank[y_root]) {
                parent[x_root] = y_root;
            } else {
                parent[x_root] = y_root;
                rank[y_root]++;
            }
        }

        private int findRoot(int[] parent, int x) {
            int x_root = x;
            while (parent[x_root] != x_root) {
                x_root = parent[x_root];
            }
            return x_root;
        }
    }
}
